Phóng viên Jason Burt của tờ The Independent từng miêu tả Benayoun hồi nhỏ: "9 tuổi cậu ấy được đánh giá là một tài năng của bóng đá. Tuổi 11 bắt đầu có danh tiếng với tài năng của mình. Tuổi 13, khuôn mặt anh xuất hiện trên trang nhất nhiều tờ báo ở Israel." [4]

Benayoun bắt đầu sự nghiệp năm 9 tuổi với Hapoel Be'er Sheva. Để đi tập, anh thường phải di chuyển 60 km cùng bố.[3] Sau khi tạo được tiếng tăm cho riêng mình, anh được các tuyển trạch viên của Ajax Amsterdam mời đến. Tại Ajax, anh mang áo số 14. Ajax còn mời luôn gia đình Benayoun cùng anh sang Hà Lan. Vào sinh nhật 16, anh trở thành cầu thủ ghi nhiều bàn nhất cho đội trẻ Ajax và là cầu thủ xuất sắc nhất, và Ajax mời anh ký hợp đồng chuyên nghiệp có thời hạn 4 năm.[4] Tuy nhiên, Benayoun và gia đình không thích nghi được với đời sống ở Amsterdam, do vậy anh từ chối bản hợp đồng và cùng gia đình trở về Israel chỉ sau 8 tháng.[4]